package com.tantou.java.struct.recusion;

public class TaijieTest {

    /**
     * 台阶
     */
    public static void main(String[] args) {
        System.out.println(fn(3));
        System.out.println(fn(4));
        System.out.println(fn(5));
        System.out.println(fn(6));
        System.out.println(fn(7));
    }

    public static int fn(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        return fn(n - 1) + fn(n - 2);
    }

    public static int notfn(int n) {

        int pre = 2;
        int prepre = 1;
        int ret = 0;
        for (int i = 3; i < n; i++) {
            ret = pre + prepre;
            prepre = pre;
            pre = ret;
        }
        return ret;
    }
}
